#在单增序列中找x或x的后继
def bin_search1(a, n, x):
    left, right = 0, n
    while left < right:
        mid = (left + right) // 2
        if x <= a[mid]:
            right = mid
        else:
            left = mid + 1
        print('[', left, right, ']')
    return left

#在单增序列中找x或x的前驱
def bin_search2(a, n, x):
    left, right = 0, n
    while left < right:
        mid = (left + right + 1) // 2
        if a[mid] <= x:
            left = mid
        else:
            right = mid - 1
        print('[', left, right, ']')
    return left

n = 5
a = [i for i in range(1, 6)]
x = 2
print(bin_search1(a, n, x) + 1)
print(bin_search2(a, n, x) + 1)
